package com.love.labuladong.queue.priority;

import java.util.PriorityQueue;

/**
 * 2208. 将数组和减半的最少操作次数
 * 贪心 + 优先队列
 * 什么样的场景符合贪心 ：每一个最优的子操作，能推导出最优的最终结果
 */
public class HalveArray2280 {

    /**
     * 使用优先队列：相当于将 nums 排序，但是此题还有一个功能，将 折半的数需要继续放入 优先队列 中
     * 这里就满足贪心 ：每次将 最大的数 折半，则将总数减小一半则最快，即操作的次数最少
     * 还有就是要考虑，累加和溢出以及折半产生小数的情况
     * @param nums
     * @return
     */
    public static int halveArray(int[] nums) {
        // 大根堆
        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
        double sum = 0;
        // 将数组中的数全部放入堆中
        for(int n : nums ){
            heap.add((double)n);
            sum += (double)n;
        }
        double target = sum / 2;
        int ans = 0;
        // mins ：折半数的累加和
        for(double mins = 0; mins < target; ans++ ){
            // 大根堆每次取出的是最大值
            double head =  heap.poll();
            double half = head / 2;
            mins += half;
            // 将折半的数重新放入队中
            heap.add(half);
        }
        return ans;
    }

    public static void main(String[] args) {
       int[] nums = {5,19,8,1};
        int i = halveArray(nums);
        System.out.println(i);
    }


}
